package 中等.贪心思想;

/**
 * 给你一个整数数组 nums ，和两个整数 limit 与 goal 。数组 nums 有
 * 一条重要属性：abs(nums[i]) <= limit 。
 * 返回使数组元素总和等于 goal 所需要向数组中添加的 最少元素数量 ，
 * 添加元素 不应改变 数组中 abs(nums[i]) <= limit 这一属性。
 * 注意，如果 x >= 0 ，那么 abs(x) 等于 x ；否则，等于 -x 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-elements-to-add-to-form-a-given-sum
 */
public class 构成特定和需要添加的最少元素_1785 {

    public static void main(String[] args) {

        System.out.println(minElements(new int[]{1, -1, 1}, 3, -4));

    }

    /**
     * 贪心
     * 求出数组和 sum , 每次新添加元素，都取最大值 limit
     * 转换思路
     * 假设 sum < goal 求的是使得 sum+n*limit >= goal 的最小值 n
     * 注意：sum 求和可能 int 溢出，使用 long 类型
     */
    public static int minElements(int[] nums, int limit, int goal) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        long diff = Math.abs(goal - sum);
        return diff % limit == 0 ? (int) (diff / limit) : (int) (diff / limit) + 1;
    }

}
